1. Field of the Invention
The present invention generally relates to methods for automatically placing pins and wiring a bit stack and, more particularly, to a method for bit stack channel wiring optimization in very large scale integrated (VLSI) bit stack design that provides an optimal or near-optimal solution, given a fixed bit stack macro placement order and combination of fixed and/or variable pin placements within each bit stack macro.
2. Description of the Background Art
In VLSI design, dataflow stacks are a series of bit-oriented macros placed on top of each other. Stacks normally consist of "structured" macros, such as data registers, multiplexers and arithmetic logic units (ALUs), usually custom-designed per bit. Bits are replicated horizontally as needed. Macros are stacked vertically to form the data flow. The inputs and outputs (I/Os) of the stack macros tend to be grouped by bit; that is, the output of, say, the third bit of a data register tends to be input to the third bit of a multiplexer, for example. Poor ordering of stack macros may not be wirable within the given circuit area constraints. Alternately, poor ordering may result in increased in stack size for wirability at the expense of die size and circuit performance.
To assist designers in this process, automated pin placement and wiring methods have been developed and implemented in computer programs. Most existing stack optimizers use total line crossings at each macro boundary to evaluate the wirability of a given stack ordering. Some assume that all bits within a macro stack are identical in size and solve the stack ordering problem by optimizing a single bit. Stacks optimized using the prior evaluation methods often have wiring overflows. Alternative approaches to the problem of optimizing wiring channels for bit stacks include manual methods or an existing knowledge optimization algorithm. Modern microprocessors contain many data stacks with various sizes, further complicating the optimization problem. Without an improved optimization algorithm and software implementation, the bit stack optimization of microprocessors is very time-consuming and error prone. Moreover, the prior art does not permit partial physical design of VLSI bit stacks prior to the availability of pin placement information. Nor does the prior art permit determining pin placements that aid bit stack wiring channel optimization.
In one approach known to the applicant, macros are moved one at a time to a "best" position, starting at the top of the order of macros. This "best" position minimizes the summation of the length of only the busses which connect to that macro. When applied throughout the stack, the process causes macros to "pull" each other together based on their interconnectivity. During this process, a subset of macros may get into a repeating order of loop. This subset of macros in the loop are grouped together and treated as a single macro. By ignoring the interconnections between the macros in the group, the group is then pulled to its optimum place in the current order. This approach relates strictly to macro placement and does not guarantee a solution that minimizes the number of wiring channels since it does not guarantee the solution is wirable. Moreover, this approach does not address the variability that exists in pin placement and how actual pin placement within macros can be used to further reduce wiring channels compared to solutions arrived at using macros with fixed pin placements.